14 Soft Limits of Computation

Algorithmics 2025

Computational Complexity Classes

  • P, NP, and NP-complete are all decision problem classes.

  • NP-hard can include decision problems or non-decision problems.

  • Decision problems have a “yes/no” answer.

  • P – solvable in polynomial time on a deterministic machine.

  • NP – solvable on a nondeterministic machine in polynomial time

    • equivalently, verifiable in polynomial time.

Reduction

Reduction means transformation.

A reduction is an algorithm for converting one problem into another.

If Problem A is reducible to Problem B:

  • Problem A can be transformed into Problem B in polynomial time.
  • If Problem B can be solved efficiently, then Problem A can also be solved efficiently.
  • Therefore, solving A is no harder than solving B.

Reduction Example

Sudoku to Graph Colouring

  1. One vertex per cell in the Sudoku grid.
  2. Edges between vertices if cells cannot contain the same number (same row, same column, or same box).
  3. Use one colour per digit.
  4. The question becomes: Is the graph 9 colourable?
  5. Graph Colouring is at least as hard as Sudoku.

NP-hard

  • Every problem in NP can be reduced to NP-hard in polynomial time.
  • Not required to be in NP.
    • May not even be a decision problem.
  • NP-hard problems that are in NP are called NP-complete.

NP-complete

  • In NP (verifiable in polynomial time).
  • Every problem in NP can be reduced to NP-complete in polynomial time
    • as hard as any problem in NP.
  • If you can solve one NP-complete problem in polynomial time, you can solve all NP problems in polynomial time.

Venn Diagram of Classifications